package _动态规划;

import java.util.Arrays;

public class xx_DP {
    // 子串、子序列、子数组
    // 线性
    // 53: 最大子数组和 :https://leetcode.cn/problems/maximum-subarray/
    public int maxSubArray(int[] nums) {
        // dp:  当前元素结尾的子数组最大和，dp[i] = max{dp[i-1] + num[i] , nums[i] }
        // ans: 全局子数组最大和
        int dp = 0, ans = nums[0];
        for (int num : nums) {
            dp = Math.max(dp + num, num);
            ans = Math.max(ans, dp);
        }
        return ans;
    }

    // 152: 乘积最大子数组：https://leetcode.cn/problems/maximum-product-subarray/description/
    public int maxProduct(int[] nums) {
        // 当前元素结尾 最大子数组积，最小子数组积，考虑三种情况：{正数、负数、当前数}
        int max = nums[0], min = nums[0];
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            int mx = max, mi = min;
            max = Math.max(mx * nums[i], Math.max(nums[i], mi * nums[i]));
            min = Math.min(mx * nums[i], Math.min(nums[i], mi * nums[i]));
            ans = Math.max(ans, max);
        }
        return ans;
    }

    // 718：最长重复子数组：https://leetcode.cn/problems/maximum-length-of-repeated-subarray/
    // dp[i][j] = 以 nums1[i-1] 和 nums2[j-1] 结尾的最长公共子数组的长度
    // 默认初始化：dp[i][0] 或 dp[0][j] 表示 一个数组为空（dp[0]不存数据，能默认初始化）
    public int findLength(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        int res = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    res = Math.max(res, dp[i][j]);
                }
            }
        }
        return res;
    }

    // 子序列 -----------------------------------------------------------------------------

    // 1134：最长公共子序列 https://leetcode.cn/problems/longest-common-subsequence/
    // dp[i][j] = text1[0..i-1] 和 text2[0..j-1] 的最长公共子序列长度
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }

    // 128: hoot 100 最长连续序列 https://leetcode.cn/problems/longest-consecutive-sequence/
    // 注意排序的时间复杂度至少是 O(N*long(N))
    public int longestConsecutive_(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Arrays.sort(nums);
        int count = 1;
        int countMax = 1;
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] + 1 == nums[i + 1]) {
                count++;
            }
            // 间断点
            if (nums[i + 1] - nums[i] > 1) {
                count = 1;
            }
            if (count > countMax)
                countMax = count;
        }
        return countMax;
    }

    // 674：最长连续递增序列：https://leetcode.cn/problems/longest-continuous-increasing-subsequence/
    // 线性扫描
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0)
            return 0;
        int maxLen = 1, con = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[i - 1]) {
                con++;
            } else {
                con = 1;
            }
            maxLen = Math.max(maxLen, con);
        }
        return maxLen;
    }

    // 300:最长递增子序列：https://leetcode.cn/problems/longest-increasing-subsequence/
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // dp[i] = i 之前包括 i 的以nums[i]结尾的最⻓递增⼦序列的⻓度
        int[] dp = new int[n];
        int res = 0;
        Arrays.fill(dp, 1); // 每个元素最短子序列为1

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }

    // 392：判断子序列：https://leetcode.cn/problems/is-subsequence/description/
    // 双指针
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;
        int n = s.length(), m = t.length();
        while (i < n && j < m) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == n;
    }


    // 115：不同的子序列：https://leetcode.cn/problems/distinct-subsequences/
    // 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。
    // dp[i][j] ：s[0..i-1] 中有多少种方式可以组成 t[0..j-1]
    public int numDistinct(String s, String t) {
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化：t为空串时，所有dp[i][0] = 1
        for (int i = 0; i <= m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // 用 或者 不用当前字符
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    // 不匹配，不能用当前字符
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[m][n];
    }

    // 76:todo  100题 最小覆盖字串：https://leetcode.cn/problems/minimum-window-substring/
    public String minWindow(String s, String t) {
        return null;
    }


    //--------------------------------------------------------------------------------
    // 回文问题汇总 //===================================================================
    // 回文问题：关键在于 遍历顺序

    // 647：回文字串 ：https://leetcode.cn/problems/palindromic-substrings/
    // dp[i][j] 表示 s[i..j] 是否是回文串
    public class Solution {
        public int countSubstrings(String s) {
            int n = s.length();
            int count = 0;
            int[][] dp = new int[n][n];

            for (int i = n - 1; i >= 0; i--) {
                for (int j = i; j < n; j++) {
                    if (s.charAt(i) == s.charAt(j)) {
                        // 包含了以两个字符为中心和 以一个字符为中心
                        if (j - i <= 1 || dp[i + 1][j - 1] == 1) {
                            dp[i][j] = 1;
                            count++;
                        }
                    }
                }
            }
            return count;
        }
    }

    // 5：todo 最长回文子串：https://leetcode.cn/problems/longest-palindromic-substring/
    // 子串 要求连续
    // dp[i][j] 表示 s[i..j] 是否是回文串
    // 如果 j 从 i + 1开始 是不会初始化一个字符情况的
    // 然后，如果写 j - i <= 1 并且不显式初始化，会让"aba"，被误判为不是回文
    //         写 j - i <= 2 是把"aba"当成了一个基本情况（不再依赖 dp[i+1][j-1]）
    //            三个字符 → 只要两端相等，中间单个字符天然是回文
    //            两个字符 → 只判断是否相等。

    // 所以（直接用这个），让 j 从 i 开始，可以写 j - i <= 1，这里隐藏了初始化
    public String longestPalindrome(String s) {
        int n = s.length();
        if (n < 2) return s;

        boolean[][] dp = new boolean[n][n];
        int maxLen = 1, start = 0;

        //  外层：i 从下往上
        //  内层：j 从左往右
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i ; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (j - i <= 1 || dp[i + 1][j - 1]) {
                        dp[i][j] = true;
                        if (j - i + 1 > maxLen) {
                            maxLen = j - i + 1;
                            start = i;
                        }
                    }
                }
            }
        }
        return s.substring(start, start + maxLen);
    }

    // 516：todo 最长回文子序列：https://leetcode.cn/problems/longest-palindromic-subsequence/
    // dp[i][j] 表示 s[i..j] 范围内的最长回文子序列的长度
    // 子序列不需要连续
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        int[][] dp = new int[n][n];

        for (int i = n - 1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i+1; j < n; j++) {
                    if (s.charAt(i) == s.charAt(j)) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;  // 区间扩大
                    }else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);  // 丢掉一个字符
                }
            }
        }
        return dp[0][n - 1];
    }


    // 125：验证回文串：https://leetcode.cn/problems/valid-palindrome/description/
    public boolean isPalindrome(String s) {
        String ss = s.replaceAll("[^0-9a-zA-Z]", "").toLowerCase();
        System.out.println(ss);
        return ss.contentEquals(new StringBuilder(ss).reverse());
    }

    // 680 ：验证回文串II：
    public boolean validPalindrome(String s) {
        int i = 0, j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return isPalindrome(s, i + 1, j) || isPalindrome(s, i, j - 1);
            }
            i++;
            j--;
        }
        return true;
    }

    private boolean isPalindrome(String s, int l, int r) {
        while (l < r) {
            if (s.charAt(l) != s.charAt(r))
                return false;
            l++;
            r--;
        }
        return true;
    }

    // 409：最长回文串：https://leetcode.cn/problems/longest-palindrome/description/
    // 返回由字符串 s 里的字符能构成的最长回文串长度
    public int longestPalindrome1(String s) {
        char[] chars = new char[152];
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            chars[s.charAt(i)]++;
            if (chars[s.charAt(i)] == 2) {
                chars[s.charAt(i)] = 0;
                ans += 2;
            }
        }
        if (ans < s.length()) ans++;
        return ans;
    }

}
